package com.zlsy.learning.leetcode.sort;

import java.util.Arrays;

/**
 * @author zhouliang
 * @date 2020/8/24 19:30
 *     <p>插入排序演示
 */
public class InsertionSort {

  public static void main(String[] args) {
    int[] a = new int[] {4, 5, 6, 1, 3, 2};
    int n = a.length;
    int[] ints = insertionSort(a, n);
    System.out.println(Arrays.toString(ints));
  }

  private static int[] insertionSort(int[] a, int n) {
    if (n <= 1) {
      return a;
    }
    for (int i = 1; i < n; i++) {
      // 未排序区第一个值
      int value = a[i];
      // 排序区最后一个值
      int j = i - 1;
      // 遍历排序区和当前未排序区的第一个值进行比较和移动
      for (; j >= 0; --j) {
        // 如果排序区值大于当前未排序区值
        if (a[j] > value) {
          // 交换位置
          a[j + 1] = a[j];
        } else {
          // 不大直接跳出
          break;
        }
      }
      // 在排序区“合适的位置”（就是比排序区某个值大的位置）插入未排序区排在第一的值
      a[j + 1] = value;
    }
    return a;
  }
}
